package com.demo.java.OD301_350.OD319;

import java.util.*;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【阿里巴巴找黄金宝箱4(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146106725
 */
public class OdMain {

    // 方法：solve_method，接受一个整数数组，返回处理后的数组
    public static int[] solve_method(int[] nums) {
        // 使用双端队列（Deque）作为栈来存储索引
        Deque<Integer> stack = new ArrayDeque<>();
        // 初始化结果数组，存储每个元素的下一个更大的元素
        int[] res = new int[nums.length];

        // 遍历输入数组
        for (int i = 0; i < nums.length; i++) {
            // 当栈不为空且当前元素大于栈顶元素对应的数组元素时
            while (!stack.isEmpty() && nums[stack.peekFirst()] < nums[i]) {
                // 弹出栈顶元素
                int index = stack.pop();
                // 将结果数组中该位置的值更新为当前元素（即下一个更大的元素）
                res[index] = nums[i];
            }
            // 将当前元素的索引压入栈中
            stack.push(i);
        }

        // 遍历栈中剩余的元素
        while (!stack.isEmpty()) {
            // 标志位，用来判断是否找到下一个更大的元素
            boolean flag = false;
            // 弹出栈顶元素
            int index = stack.pop();
            // 再次遍历数组，查找比当前元素大的元素
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > nums[index]) {
                    flag = true;
                    res[index] = nums[i];
                    break;
                }
            }
            // 如果没有找到比当前元素大的元素，将该位置的值设为-1
            if (!flag) {
                res[index] = -1;
            }
        }
        // 返回最终结果数组
        return res;
    }

    public static void main(String[] args) {
        // 创建Scanner对象来读取输入
        Scanner in = new Scanner(System.in);

        // 读取一行输入，并将其转换为整数数组
        int[] nums = Arrays.stream(in.nextLine().split(",")).mapToInt(
                Integer::parseInt).toArray();

        // 调用solve_method方法，得到处理后的结果数组
        int[] result = solve_method(nums);

        // 用于存储输出结果的字符串
        String ret = "";

        // 遍历结果数组，将每个结果元素添加到字符串中
        for (int num : result) {
            ret += num + ",";  // 用逗号分隔
        }

        // 输出最终结果，去掉字符串最后的逗号
        System.out.println(ret.substring(0, ret.length() - 1));
    }
}
